function quickSort(arr) {
    //input your code here
    // let left: number = 0;
    // let right: number = arr.length - 1
    // if (left < right) {
    //   let i: number = left
    //   let j: number = right
    //   let x = arr[left]
    //   while(i < j) {
    //     while(i < j && arr[j] >= x)  // 从右向左找第一个小于x的数
    //     j--;
    //     if (i < j) {
    //       arr[i++] = arr[j]
    //     }
    //     while(i < j && arr[i] < x)   // 从左向右找第一个大于等于x的数
    //     i++
    //     if (i < j) {
    //       arr[j--] = arr[i]
    //     }
    //   }
    //   arr[i] = x
    //   quickSort(arr, l, i - 1); // 递归调用 
    //   quickSort(arr, i + 1, r);
    // } 
    // return arr
    // let index = Math.floor(arr.length / 2)
    // while(index > 0) {
    //   for (let i = 0; i < arr.length; i++) {
    //     let n = i
    //     while(arr[n] < arr[n - index] && n > 0) {
    //       let temp = arr[n]
    //       arr[n] = arr[n - index]
    //       arr[n - index] = temp
    //       n = n - index
    //     }
    //   }
    //   index = Math.floor(arr.length / 2)
    // }
    // return arr
    // if (arr.length <= 1) { return arr }
    // // 取基准值
    // var index = Math.floor(arr.length / 2);      // 基准值的索引
    // var pivot = arr.splice(index, 1)[0];         // 将基准值赋给变量 pivot 并从数组中将其删除
    // var left: any = [];		// 存放基准值左边的数据
    // var right: any = [];		// 存放基准值右边的数据
    // for (var i = 0; i < arr.length; i++) {
    //   if (arr[i] < pivot) {
    //     left.push(arr[i]);	   // 小于基准值存入 left 中
    //   } else {
    //     right.push(arr[i]);	// 大于基准值存入 right 中
    //   }
    // }
    // return quickSort(left).concat([pivot], quickSort(right));	// 递归调用
    if (arr.length <= 1)
        return arr;
    // 选择第 0 个作为基准，定义两个数组
    var pivot = arr[0];
    var left = [];
    var right = [];
    // 删除基准值
    arr.shift();
    // 数值分类
    arr.forEach(function (item) {
        item < pivot ? left.push(item) : right.push(item);
    });
    return quickSort(left).concat([pivot], quickSort(right));
}
function generateCases(length, step) {
    if (step === void 0) { step = 1; }
    var a = [];
    var value = 0;
    for (var i = 0; i < length; i++) {
        a.push(value);
        value += step;
    }
    var tmp;
    for (var i = 0; i < length; i++) {
        var f = Math.random() * (length - i);
        var r = i + Math.floor(f);
        tmp = a[r];
        a[r] = a[i];
        a[i] = tmp;
    }
    return a;
}
function checkRes(arr, step) {
    for (var i = 0; i < arr.length - 1; ++i) {
        if (arr[i] + step !== arr[i + 1])
            return false;
    }
    return true;
}
function testQuickSort() {
    for (var i = 6; i <= 100000; i = i * 2) {
        var randomStep = Math.ceil(Math.random() * 10);
        var arr = generateCases(i, randomStep);
        var start = Date.now();
        var ret = quickSort(arr);
        var end = Date.now();
        console.log("Quick sort for ".concat(i, " numbers costs ").concat(end - start, "ms"));
        if (!checkRes(ret, randomStep)) {
            console.log("Fail");
            return false;
        }
        else {
            console.log("Passed");
        }
    }
    return true;
}
testQuickSort();
//quickSort([ 60, 66, 90, 30, 96, 42, 6, 84, 0, 24, 18, 54, 48, 78, 102, 36, 72, 12 ])
